/*
 * @lc app=leetcode.cn id=561 lang=javascript
 *
 * [561] 数组拆分 I
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function (nums) {
  let result = 0;
  const maxPQ = new MaxPQ();
  for (const n of nums) {
    maxPQ.insert(n);
  }
  for (let i = 0; i < nums.length; i++) {
    if (i % 2 !== 0) {
      result += Math.min(maxPQ.delTop(), maxPQ.delTop());
    }
  }
  return result;
};

class MaxPQ {
  constructor() {
    this.pq = [];
    this.size = 0;
  }
  less(i, j) {
    return this.pq[i] < this.pq[j];
  }
  exch(i, j) {
    [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
  }
  swin(k) {
    while (k > 0 && this.less((k - 1) >> 1, k)) {
      this.exch((k - 1) >> 1, k);
      k = (k - 1) >> 1;
    }
  }
  sink(k) {
    while (k * 2 + 1 < this.size) {
      let j = k * 2 + 1;
      if (j < this.size && this.less(j, j + 1)) {
        j++;
      }
      if (this.less(j, k)) {
        return;
      }
      this.exch(k, j);
      k = j;
    }
  }
  insert(val) {
    this.pq.push(val);
    this.swin(this.size++);
  }
  delTop() {
    let top = this.pq[0];
    this.exch(0, this.size - 1);
    this.pq.pop();
    this.size--;
    this.sink(0);
    return top;
  }
}

// @lc code=end
